import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

class Main{
    public static void main(String[] args) {
        int i = 1;
        System.out.println(i);
    }
}


class Solution {
     static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      public TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
         this.right = right;
      }
  }

    public String tree2str1(TreeNode root)
    {
        if(root == null) return "";

        if(root.left == null && root.right == null){
            return Integer.toString(root.val);
        }

        StringBuilder st = new StringBuilder();

        st.append(root.val);

        if(root.left == null){
            if(root.right == null){
                return "";
            }else{
                st.append("()");
                st.append("(");
                st.append(tree2str(root.right));
                st.append(")");
            }
        }else{
            if(root.right == null){
                st.append("(");
                st.append(tree2str1(root.left));
                st.append(")");
            }else{
                st.append("(");
                st.append(tree2str(root.left));
                st.append(")");
                st.append("(");
                st.append(tree2str(root.right));
                st.append(")");
            }

        }

        return st.toString();
    }
    public String tree2str(TreeNode root) {
        if(root.left == null && root.right == null){
            return Integer.toString(root.val);
        }

        return tree2str1(root);
    }

    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);
        TreeNode n4 = new TreeNode(4);

        n1.left = n2;
        n2.right = n3;
        n3.left = n4;

        Solution s = new Solution();
        System.out.println(s.tree2str(n1));

    }
}

class Solution1 {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        public TreeNode(int val) { this.val = val; }
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null) return new LinkedList<Integer>();

        List<Integer> list = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();

        TreeNode cur = root;
        stack.push(root);
        while(!stack.empty() || cur.left != null){
            while(cur.left != null){
                stack.push(cur.left);
                cur = cur.left;
            }

            TreeNode t = stack.pop();
            list.add(t.val);

            if(t.right != null){
                cur = t.right;
                stack.push(t.right);
            }
        }
        return list;
    }

    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);

        n1.right = n2;
        n2.left = n3;

        Solution1 s = new Solution1();
        System.out.println(s.inorderTraversal(n1));
    }
}